package dp.maxsum;

public class leetcode363矩形区域不超过K的最大数值和 {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int min = Integer.MAX_VALUE;
        int[][] sum = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0) {
                    sum[i][j] = matrix[i][j];
                } else {
                    sum[i][j] = sum[i - 1][j] + matrix[i][j];
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                int[] nums = new int[col];
                for (int l = 0; l < col; l++) {
                    if (j == 0) {
                        nums[l] = sum[j][l];
                    } else {
                        nums[i] = sum[i][l] - sum[j - 1][l];
                    }
                }
                int tempMin = minDisLine(nums, k);
                min = Integer.min(tempMin, min);
            }
        }
        return k - min;
    }

    private int minDisLine(int[] nums, int k) {
        int length = nums.length;
        int tempMin = Math.abs(k -nums[0]);
        int min = Math.abs(k - nums[0]);
        for (int i = 1; i < length; i++) {
            tempMin = Integer.min(Math.abs(k - nums[i]), k - (nums[i] + k - tempMin));
            min = Integer.min(min, tempMin);
        }
        return min;
    }
}
